package hot_100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author: Darven
 * @createTime: 2025-10-04  23:46
 * @description: TODO
 */
public class P78 {


    // 用于收集子集的列表
    private List<Integer> res;
    public List<List<Integer>> subsets(int[] nums) {
        // 答案集合
        List<List<Integer>> ans=new ArrayList<>();
        // 添加空的子集
        ans.add(new ArrayList<>());
        // 通过1，2，3去找对应子集，1，下面有2，3 2下面有3，3下面没有了，这样就能确保不会有重复
        // 因此不需要set来去重，可以节省空间，以及不用集合复制，减少空间复杂度
        for (int i=0;i<nums.length;i++){
            // 创建新的子集集合，避免重复
            res=new ArrayList<>();
            dfs(i,nums,ans);
        }
        // 转化成
        return ans;
    }

    // 深搜
    private void dfs(int i, int[]nums, List<List<Integer>> ans){
        // 如果子集到达nums最大深度就返回
        if(res.size()== nums.length){
            return;
        }
        // 直接添加
        res.add(nums[i]);
        ans.add(new ArrayList<>(res));
        // 遍历1下面的2和3
        for(int j=i+1;j<nums.length;j++){
            dfs(j, nums, ans);
            // 回溯删除最后一个
            res.removeLast();
        }
    }
}
